package sword.T60;

import java.util.Arrays;

/**
 * @Author: 18362
 * @Create: 2022-04-10 15:11:45 星期日
 */
class Solution {
    // 解法一：dfs，复杂度O(6^n)
    /*public double[] dicesProbability(int n) {
        int[] cnt = new int[6*n+1];
        dfs(cnt, 0, 0, n);
        double[] res = new double[5*n+1];
        int total = 1;
        for (int i=0; i<n; ++i)
            total *= 6;
        for (int i=n; i<=6*n; ++i) {
            res[i-n] = 1.0 * cnt[i] / total;
        }
        return res;
    }

    private void dfs(int[] cnt, int sum, int cur, int n) {
        if (cur == n) {
            cnt[sum]++;
            return;
        }
        for (int i=1; i<=6; ++i) {
            dfs(cnt, sum+i, cur+1, n);
        }
    }*/

    // 解法二：动态规划，复杂度O(n2)
    public double[] dicesProbability(int n) {
        int[] dp = new int[6*n+1], temp = new int[6*n+1];
        Arrays.fill(dp, 1, 7, 1);
        for (int i=2; i<=n; ++i) {
            for (int j=i-1; j<=6*i-6; j++) {
                for (int k=1; k<=6; ++k)
                    temp[j+k] += dp[j];
            }
            System.arraycopy(temp, i, dp, i, 5*i+1);
            Arrays.fill(temp, 0);
        }
        double[] res = new double[5*n+1];
        int total = 1;
        for (int i=0; i<n; ++i)
            total*=6;
        for (int i=n; i<=6*n; ++i)
            res[i-n] = 1.0 * dp[i] / total;
        return res;
    }
}